🎁 Subset Sum Count for Charity Gifts

Help Emma count gift combinations that match the donation target

👩‍💻 Emma's Charity Gift Challenge

🎯 The Mission:

Help Emma count the number of different gift item combinations that sum exactly to the donation target, then apply her event rule (count * 2 + 10).

📋 Requirements:

  • Count subsets of gift values that sum to the target
  • Handle 1 to 10 items, values from 1 to 100, target from 1 to 100
  • Output the count, then (count * 2 + 10)

Input/Output Specifications

  • Input: Integer n (number of items), n space-separated integers (gift values), integer sumValue (target)
  • Output: First line: number of subsets; Second line: count * 2 + 10

Example: values = [1, 2, 3, 4, 5, 6], target = 7

Values:

1
2
3
4
5
6

Output: 4
18
(Subsets: [1,2,4], [1,3,3], [2,5], [3,4])

Example: values = [2, 4, 6, 10, 12], target = 16

2
4
6
10
12

Output: 3
16
(Subsets: [2,4,10], [4,12], [6,10])

⚡ Subset Sum Count Explained

How Subset Sum Count Works

  1. Dynamic Programming: Use a DP table where dp[i][j] is the number of subsets using the first i items that sum to j
  2. Fill Table: For each item and sum, add the number of subsets with and without the current item
  3. Compute Result: Output dp[n][target], then apply (count * 2 + 10)

DP Table Example (values = [1, 2, 3], target = 6)

Value \ Sum0123456
01000000
11100000
21111000
31112111

Count: 1, Result: 1 * 2 + 10 = 12 (Subset: [3,3])

Time Complexity

O(n * sumValue)

For filling the DP table

Space Complexity

O(n * sumValue)

For the DP table

Why Subset Sum Count?

  • ✅ Counts all possible combinations efficiently
  • ✅ Useful in resource allocation and combinatorics
  • ✅ Simple DP approach
  • ❌ Space-intensive for large target sums

🔍 Step-by-Step Subset Sum Count Demo

Click "Start Demo" to begin step-by-step visualization

Algorithm Progress:

1. Display input values and target
2. Build DP table
3. Display result

Current Values:

DP Table (Value \ Sum):

🎮 Practice Subset Sum Count

Enter values and target, then click "Count Combinations"

Test Cases

Example 1: values = [1, 2, 3, 4, 5, 6], target = 7 → 4
18

Example 2: values = [2, 4, 6, 10, 12], target = 16 → 3
16

📊 Algorithm Analysis

Subset Sum Count Process

  1. Initialize DP: Set dp[i][0] = 1 (empty subset) and dp[0][j] = 0 for j > 0
  2. Fill DP Table: For each item i and sum j, dp[i][j] = dp[i-1][j] + dp[i-1][j - value[i-1]] if value[i-1] ≤ j
  3. Output: Print dp[n][target], then (count * 2 + 10)

Time Complexity

O(n * sumValue)

For filling the DP table

Space Complexity

O(n * sumValue)

For the DP table

Key Points

  • Dynamic Programming: Counts all subsets efficiently
  • Combinatorial: Sums subsets with and without each item
  • Applications: Resource allocation, combinatorics
  • Limitation: Space-intensive for large target sums